Subject: Re: Hash function for strings
From: [email-masked] (Ozan S. Yigit)
Date: Thu, 3 Mar 1994 20:54:16 GMT
Newsgroups: comp.programming

AMUNDSEN JARLE/3AA/D:

   I am trying to find a good hash function for strings, names that is, and
   wonder if anyone has an idea on how good such a function can hash. Given
   that the keys are not known in advance.

there are several good multiplicative ones, eg.

        33      due to dan bernstein [h = (h << 5) + h + c]
        131     due to gonnet/baeza-yates ("Handbook")
	65599	due to me (sdbm) [h = (h << 6) + (h << 16) - h + c]

there are also a bunch of scramble-type functions, eg. peter honeyman's
crc-hash routine from pathalias, or the one from lcc [str and list mgmt
module]. have you looked at those?

   The function I found to be best, starts at the end of the string and 
   recursively shifts the hash of the previous character n times to the left and
   subtracts m, and adds the shift and subtraction of the current character.

is n a constant or the index of the current char? m is the table size?

oz
---
C++ was invented because Vogon poetry | electric: [email-masked]
wasn't destructive enough. -anonymous | ph:[416] 736 2100 x 33976